package com.algorithm.learning.base.贪心算法;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/8/26 23:40
 **/
public class 初识贪心 {

    /**
     * 题目：给出一个字符串数组，将数组中的字符串进行拼接，并进行排序，找到最小拼接字符串的情况！
     *
     * 所谓字符串的排序，可以看成是一个K进制的数进行比较，例如：a < b, b < c, ... ac < bc, ad < bc ... 所以字符串的排序，规则如下：
     * 1、如果多个字符串相等的情况下，哪个首字符串小，那么这个字符串就小，如果首字符串相同，就比较下一个字符串，以此类推
     * 2、如果多个字符串不相等的情况下，那么将少的那个字符串补上0，在比较，例如 ac 与 b相比较，我们可以将 b 看成 b0, 而 a < b, 所以 ac < b0, 所以 ac < b
     *
     * 例如：给一个字符串数组[bc, as, wd, xm, ac]
     * 那么拼接字符串的情况有很多，例如：bcaswdxmac, bcwdasxm, bcwdxmasc... 按照数学计算，应该有 5! 个结果。
     * 那么，如何找到最小拼接字符串的情况呢？
     *
     * 第一种解法：
     * 暴力解决。直接将所有拼接的字符串全部收集起来，然后在排序，找到最小的。
     *
     * 第二种解法：
     * 我们可以证明，数组前面字符串+后面字符串的值，一定是 小于 后面字符串+前面字符串的值。
     *
     * 所以我们只要将，前面字符串+后面字符串的值，进行排序，那么，最小的拼接字符串就是最小的。
     * [bc, as, wd, xm, ac] => bc+as >= as + bc，那么排序为[as, bc, wd, xm, ac], 一直排下去，最后的结果就是[ac, as, bc, wd, xm]
     *
     * 那么此时数组从头到尾拼接，就是最小的字符串
     *
     * @param strs
     */
    public static String lowestString(String[] strs) {
        if (strs == null || strs.length == 0) {
            return null;
        }
        // 此时数组中的字符串就已经排好序了
        Arrays.sort(strs, new StrComparator());

        String res = "";
        for (int i = 0; i < strs.length; i++) {
            res += strs[i];
        }
        return res;
    }

    public static class StrComparator implements Comparator<String> {

        @Override
        public int compare(String o1, String o2) {
            return (o1 + o2).compareTo(o2 + o1);
        }
    }
}
